package arithmetic;

/**
 * @Author: Jie
 * @Date: 2019/3/21 9:40
 * @Function : leetcode 70 爬楼梯 动态规划
 *最优斐波那契额  nlogn 原理待解答 线性代数：矩阵乘法
 */
public class A_26_ClimbingStairs {

    public static void main(String[] args) {
        int i = climbStairs(3);
        System.out.println(i);
    }

    //斐波那切数列 一种形式
    //优化二：时间复杂度O(N)  空间复杂度O(1)
    public static int climbStairs(int n) {
//    f0=1 f1=1 f2=2; f3=3;
//    fn = fn-1 + fn-2;
        if (n == 1 | n==0){
            return 1;
        }
        int [] temp =new int[n+1];
        temp[0] =1;
        temp[1] =1;
        for (int i = 2; i <= n ; i++) {
            temp[i]=temp[i-1] +temp[i-2];
        }
        return temp[n];
    }

    //斐波那切数列 一种形式
    //优化二：时间复杂度O(N)  空间复杂度O(1)
    public static int climbStairs2(int n) {
//    f0=1 f1=1 f2=2; f3=3;
//    fn = fn-1 + fn-2;
        if (n == 1 | n==0){
            return 1;
        }
        int current = 0;
        int pre1=1;
        int pre0=1;
        for (int i = 2; i <= n ; i++) {
            current = pre1 + pre0;
            pre0 = pre1;
            pre1 = current;
        }
        return current;
    }
}
